#python program for counting sort (updated)
n=int(input("please give the number of elements\n"))
tlist = list()
print("okey now plase give the elemets")
for i in range(n):
  tlist.append(int(input("\n")))
k = max(tlist)
n = len(tlist)


def counting_sort(tlist, k, n):
 
    """ Counting sort algo with sort in place.
        Args: 
            tlist: target list to sort
            k: max value assume known before hand
            n: the length of the given list
            map info to index of the count list.
        Adv:
            The count (after cum sum) will hold the actual position of the element in sorted order
            Using the above, 
            
    """

    # Create a count list and using the index to map to the integer in tlist.
    count_list = [0]*(k+1)

    # iterate the tgt_list to put into count list
    for i in range(0,n):
        count_list[tlist[i]] += 1  
        
    # Modify count list such that each index of count list is the combined sum of the previous counts 
    # each index indicate the actual position (or sequence) in the output sequence.
    for i in range(1,k+1):
        count_list[i] = count_list[i] + count_list[i-1]
 
    flist = [0]*(n)
    for i in range(n-1,-1,-1):
      count_list[tlist[i]] =count_list[tlist[i]]-1 
      flist[count_list[tlist[i]]]=(tlist[i])

    return flist

flist = counting_sort(tlist, k, n)
print(flist)

